package cn.zifangsky.graph;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.queue.Queue;
import cn.zifangsky.stack.LinkStack;
import cn.zifangsky.stack.Stack;

import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.List;

/**
 * 最短路问题
 *
 * @author zifangsky
 * @date 2019/1/25
 * @since 1.0.0
 */
public class ShortPath {

    private GraphList graphList;

    public ShortPath(GraphList graphList) {
        this.graphList = graphList;
    }


    /**
     * 无权图中的最短路径
     * <p>实现思路：</p>
     * <ul>1. 使用宽度优先搜索从起点开始逐个遍历当前顶点的相邻顶点</ul>
     * <ul>2. 如果某个邻接顶点没有被访问过，则将其添加到队列，并标识为已被访问，如果其路径长度（从起点到该顶点的路径长度）还没有被初始化，则更新路径长度</ul>
     * <ul>3. 逐渐将队列中的已被访问的顶点出队，并反复执行上面两步，直到找到结束顶点为止</ul>
     * <p>时间复杂度：O(V+E)</p>
     * @author zifangsky
     * @date 2019/1/25 16:55
     * @since 1.0.0
     * @param startNode 起始顶点
     * @param endNode 结束顶点
     */
    public void unWeightedShortPath(String startNode, String endNode){
        //图中的顶点数
        int vertexNum = graphList.getVertexNum();
        //所有顶点
        List<String> vertexList = graphList.getVertexList();
        //所有顶点信息
        GraphList.VertexNode[] list = graphList.getList();
        //定义一个队列
        Queue<Integer> queue = new LinkQueue<>();
        //定义一个栈
        Stack<String> stack = new LinkStack<>();

        //标识每个顶点是否被访问
        boolean[] visited = new boolean[vertexNum];
        //标识路径长度
        int[] pathArray = new int[vertexNum];
        //访问某个顶点的上一个顶点的索引
        int[] lastVertexArray =  new int[vertexNum];

        //1. 初始化
        for(int i = 0; i < vertexNum; i++){
            visited[i] = false;
            //初始路径长度为-1，表示不可达
            pathArray[i] = -1;
            //初始的上一个顶点的索引为-1，表示还没被其他顶点访问
            lastVertexArray[i] = -1;
        }

        //2. 获取起始和结束顶点在图中的位置
        int startIndex = vertexList.indexOf(startNode);
        int endIndex = vertexList.indexOf(endNode);
        if(startIndex < 0){
            throw new RuntimeException(MessageFormat.format("起始顶点不在图中：{0}", startNode));
        }
        if(endIndex < 0){
            throw new RuntimeException(MessageFormat.format("结束顶点不在图中：{0}", startNode));
        }

        queue.push(startIndex);
        pathArray[startIndex] = 0;

        //3. 如果队列不为空，则一直遍历
        loop : while (!queue.isEmpty()){
            //3.1 先出队，获取顶点索引
            int vertexIndex = queue.pop();
            //当前遍历的顶点
            GraphList.VertexNode current = list[vertexIndex];


            //3.2 然后使用宽度优先搜索遍历当前顶点的相邻顶点
            GraphList.EdgeNode temp = current.getEdgeNode();
            while (temp != null){
                //相邻顶点的索引
                int index = vertexList.indexOf(temp.getEndVertex());
                if(!visited[index]){
                    //3.3 将该顶点添加到队列，并标识为已被访问
                    queue.push(index);
                    visited[index] = true;
                }

                int newPath = pathArray[vertexIndex] + 1;
                //3.4 如果该顶点的路径长度还没有被初始化，则更新路径长度
                if(pathArray[index] < 0){
                    //更新路径长度
                    pathArray[index] = newPath;
                    //更新来至上一个顶点的索引
                    lastVertexArray[index] = vertexIndex;
                }

                //3.5 如果已经找到结束顶点，则退出外层循环
                if(temp.getEndVertex().equals(endNode)){
                    break loop;
                }else{
                    temp = temp.next;
                }
            }
        }

        //4. 遍历得到访问路径
        if(pathArray[endIndex] < 0){
            System.out.println(MessageFormat.format("顶点 {0} 和顶点 {1} 之间不存在访问路径！", startNode, endNode));
        }else{
            System.out.println("路径长度：" + pathArray[endIndex]);

            //最终点往起始点查找，并加入到栈中，用于接下来遍历形成路径
            int temp = endIndex;
            while (lastVertexArray[temp] >= 0){
                stack.push(vertexList.get(temp));
                temp = lastVertexArray[temp];
            }

            System.out.print(startNode);
            while (!stack.isEmpty()){
                System.out.print(" --> " + stack.pop());
            }
        }
    }


    /**
     * 使用 Dijkstra算法 求有权图中的最短路径
     * <p>实现思路：</p>
     * <ul>1. 使用宽度优先搜索从起点开始逐个遍历当前顶点的相邻顶点</ul>
     * <ul>2. 如果某个邻接顶点没有被访问过（还没有初始化从起点到该顶点的路径信息），则将其添加到队列</ul>
     * <ul>3. 如果从起点到该顶点的新访问路径比已经存在的旧访问路径短，则更新其访问路径和路径长度</ul>
     * <ul>4. 逐渐将队列中的顶点出队，并反复执行上面三步，直到队列为空为止</ul>
     * <p>时间复杂度：O(V+E)</p>
     * @author zifangsky
     * @date 2019/1/28 11:41
     * @since 1.0.0
     * @param startNode 起始顶点
     * @param endNode 结束顶点
     */
    public void dijkstraShortPath(String startNode, String endNode){
        //图中的顶点数
        int vertexNum = graphList.getVertexNum();
        //所有顶点
        List<String> vertexList = graphList.getVertexList();
        //所有顶点信息
        GraphList.VertexNode[] list = graphList.getList();
        //定义一个队列
        Queue<Integer> queue = new LinkQueue<>();
        //定义一个存储顶点状态的数组
        Node[] nodes = new Node[vertexNum];

        //1. 获取起始和结束顶点在图中的位置
        int startIndex = vertexList.indexOf(startNode);
        int endIndex = vertexList.indexOf(endNode);
        if(startIndex < 0){
            throw new RuntimeException(MessageFormat.format("起始顶点不在图中：{0}", startNode));
        }
        if(endIndex < 0){
            throw new RuntimeException(MessageFormat.format("结束顶点不在图中：{0}", startNode));
        }

        queue.push(startIndex);
        nodes[startIndex] = new Node(vertexList.get(startIndex));

        //2. 如果队列不为空，则一直遍历
        while (!queue.isEmpty()){
            //2.1 先出队，获取顶点索引
            int vertexIndex = queue.pop();
            //当前遍历的顶点
            GraphList.VertexNode current = list[vertexIndex];

            //2.2 然后使用宽度优先搜索遍历当前顶点的相邻顶点
            GraphList.EdgeNode temp = current.getEdgeNode();
            while (temp != null){
                //相邻顶点的索引
                int index = vertexList.indexOf(temp.getEndVertex());
                //获取通过这条路径到相邻顶点的长度（旧长度 + 边的权重）
                int tempPathCount = nodes[vertexIndex].pathCount + temp.getWeight();

                //2.3 如果顶点信息为空（该顶点还没被访问），则将该顶点添加到队列
                if(nodes[index] == null){
                    queue.push(index);
                }

                //2.4 如果新访问路径比旧访问路径短，则更新访问路径
                if(nodes[index] == null || tempPathCount < nodes[index].pathCount){
                    // 重新初始化顶点信息
                    List<String> tempPathList = new ArrayList<>(nodes[vertexIndex].pathList);
                    tempPathList.add(vertexList.get(index));
                    nodes[index] = new Node(tempPathCount, tempPathList);
                }

                temp = temp.next;
            }
        }

        //3. 输出访问路径
        if(nodes[endIndex] == null){
            System.out.println(MessageFormat.format("顶点 {0} 和顶点 {1} 之间不存在访问路径！", startNode, endNode));
        }else{
            System.out.println("路径长度：" + nodes[endIndex].pathCount);

            List<String> result = nodes[endIndex].pathList;
            for(int i = 0; i < result.size(); i++){
                if(i == 0){
                    System.out.print(result.get(i));
                }else{
                    System.out.print(" --> " + result.get(i));
                }
            }
        }
    }


    /**
     * 表示使用Dijkstra算法访问的顶点状态
     */
    class Node{
        /**
         * 从起始顶点到该顶点的路径长度
         */
        private int pathCount;
        /**
         * 从起始顶点到该顶点的路径
         */
        private List<String> pathList;

        public Node(String vertexName) {
            pathCount = 0;
            pathList = new ArrayList<>();
            pathList.add(vertexName);
        }

        public Node(int pathCount, List<String> pathList) {
            this.pathCount = pathCount;
            this.pathList = pathList;
        }

        public int getPathCount() {
            return pathCount;
        }

        public List<String> getPathList() {
            return pathList;
        }
    }


}
